//Doppelt verkettete Liste (vollständige Verwaltung)

#include <conio.h>
#include <iostream>

using namespace std;

struct Knoten
        {
         int inh;
	     Knoten *next, *prev;
	    };
	    
Knoten * wurzel=NULL, * rwurzel=NULL;


//Einfuegen am Kopf
void InsertHead(Knoten * &wurzel)
{
 Knoten * neu;
 neu=new Knoten;
 int wert;
 cout<<"Wert waehlen: ";
 cin>>wert;
 neu->inh=wert;
 neu->next=wurzel;
 neu->prev=NULL;
 if (wurzel==NULL)
 {
  rwurzel=neu;
 }
 else
 {
  wurzel->prev=neu;
 }
 wurzel=neu; 
}

//Ausgabe der Liste von vorn
void Out(Knoten * wurzel)
{
 Knoten * hilfsz=wurzel;
 cout<<"Wurzel";
 if (wurzel!=NULL) 
 while (hilfsz!=NULL)
 {
  cout<<"->"<<hilfsz->inh;
  hilfsz=hilfsz->next;
 }
 cout<<"->NULL";
 getch();
}


//Ausgabe der Liste von hinten
void ROut(Knoten * rwurzel)
{
 Knoten * hilfsz=rwurzel;
 cout<<"Rwurzel";
 if (rwurzel!=NULL) 
 while (hilfsz!=NULL)
 {
  cout<<"->"<<hilfsz->inh;
  hilfsz=hilfsz->prev;
 }
 cout<<"->NULL";
 getch();
}

//Einfuegen am Ende
void InsertTail(Knoten * &wurzel)
{
 Knoten * neu;
 neu=new Knoten;
 int wert;
 cout<<"Wert waehlen: ";
 cin>>wert;
 neu->inh=wert;
 neu->next=NULL;
 neu->prev=rwurzel;
 if (wurzel==NULL)
 {
  wurzel=neu;
 }
 else
 {
  rwurzel->next=neu;
 }
 rwurzel=neu; 
}

//Loeschen eines Elementes
void DelElement(Knoten * &wurzel)
{
 if (wurzel!=NULL)
  {
   int what;
   cout<<"Zu loeschenden Wert waehlen: ";
   cin>>what;
   Knoten *hilfsz=wurzel, * vorhilf=NULL;
   while (hilfsz!=NULL && hilfsz->inh!=what)
   {
    vorhilf=hilfsz;
    hilfsz=hilfsz->next;
   }
   if (hilfsz!=NULL)
    {
     if (vorhilf==NULL) wurzel=hilfsz->next; else vorhilf->next=hilfsz->next;
     delete hilfsz;
     cout<<"Element wurde geloescht!";
    } 
    else cout<<"Nicht vorhanden!\n";  
  }
  else cout<<"Liste leer!\n"; 
  getch();
}

//Loeschen der ganzen Liste
void DestroyList(Knoten * &wurzel)
{
 Knoten *hilfsz;
 while (wurzel != NULL)
 {
  hilfsz=wurzel;
  wurzel=wurzel->next;
  delete hilfsz;
 }
  cout<<"Speicher wurde freigegeben!";
  rwurzel=NULL;
  getch();
}


//Suchen eines Elementes
void Search(Knoten * wurzel)
{
 if (wurzel!=NULL)
  {
   int what;
   cout<<"Zu loeschenden Wert waehlen: ";
   cin>>what;
   Knoten *hilfsz=wurzel;
   while (hilfsz!=NULL && hilfsz->inh!=what)
   {
    hilfsz=hilfsz->next;
   }
   if (hilfsz!=NULL)
    cout<<"Element ist enthalten!"; 
   else cout<<"Element ist nicht enthalten!"; 
  }
  else
  cout<<"Liste ist leer!";
  getch(); 
}

void Sort(Knoten * &wurzel)
{
 int puffer, getauscht;
 Knoten *hilfsz;
 if (wurzel!=NULL)
 do
 {
  hilfsz=wurzel;
  getauscht=0;
  while (hilfsz->next!=NULL)
   {
    if (hilfsz->inh>hilfsz->next->inh)
    {
     puffer=hilfsz->inh;
     hilfsz->inh=hilfsz->next->inh;
     hilfsz->next->inh=puffer;
     getauscht=1;
    }
    hilfsz=hilfsz->next;
   } 
 } while (getauscht==1);
 cout<<"Liste wurde sortiert!";
 getch();
}

int main()
{
 char wahl;
 do
 {
  system("cls");
  cout<<"Menue: Listenverwaltung (doppelt verkettete Liste)\n";
  cout<<"1-Ausgabe (von vorn)\n2-Ausgabe (von hinten)\n3-Einfuegen Kopf\n\
4-Einfuegen hinten\n5-Loesche Element\n6-Loesche Liste\n7-Suche\n8-Sort\n\
0-Ende\n__________________________________________________\n";
  wahl=getch();
  switch(wahl)
  {
   case'1':Out(wurzel);break;
   case'2':ROut(rwurzel);break;
   case'3':InsertHead(wurzel);break;   
   case'4':InsertTail(wurzel);break;
   case'5':DelElement(wurzel);break;
   case'6':DestroyList(wurzel);break;
   case'7':Search(wurzel);break;
   case'8':Sort(wurzel);break;
  }
 } while (wahl!='0');
 return 0;
}